Re: passwd hashing algorithm
David Miller (isdmill@gatekeeper.ddp.state.me.us)
Wed, 19 Apr 1995 14:25:23 -0400 (EDT)
On Wed, 19 Apr 1995, David A. Wagner wrote:
> >
> > > 1. 25 iterations of DES with the first 8 bytes of the
> > > password as key, followed by 25 iterations of DES
> > > with the second 8 bytes of password as key.
> [ ... better version deleted ... ]
> > > (1) can be broken on a workstation with ~ 2^32 steps (and
> > > very little in the way of memory);
> >
> > I've never seen anything resembling a convincing argument for this point.
> >
>
> Hrmm, well, I could give you the crypto explanation...do you
> want me to? [Keywords: meet-in-the-middle, birthday attack]
Meet in the middle? You have enough space to make that practical?
Correct me if I'm wrong, but meet-in-the-middle means that you're going
to do the first part *and save all the output* , then do the last part
(backwards) to check if it matches any of the stored strings.
Check my math here, cause I often slip up.....
You're going to store 2^56 strings of 8 bytes, then compare the result of
2^56 operations to those 2^56 stored strings?
Can I have a workstation like that? :) :)
You've obviously got something else in mind. By all means, please tell
me how you're going to do it in 2^32 DES steps (still 2^35 (32 GB) bytes of
storage, a non-trivial sum.) Details and crypto-babble welcome:)
>
> If not, I issue you a challenge. I've included a small
> program at the end which implements (1) using libdes:
[challenge deleted]
I'll be happy to try it if you're serious about throwing that many
resources at it. First, tho, I'd kind of like to hear the theory behind
it:)
--- David
----------------------------------------------------------------------------
It's *amazing* what one can accomplish when
one doesn't know what one can't do!